package com.kevin.Code.Array;

/**
 * @author Vinlee Xiao
 * @Classname Leetcode_41
 * @Description Leetcode 41. 缺失的第一个正数 难度 困难 思路想到一半
 * @Date 2021/11/29 21:39
 * @Version 1.0
 */
public class Leetcode_41 {

    /**
     * 思路：官方题解很巧妙
     *
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {

        int len = nums.length;
        //1.将小于1的数全部置于 n+1
        for (int i = 0; i < len; i++) {

            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
        }

        //只求出大小在1-N之间的数
        for (int i = 0; i < len; i++) {
            //加绝对值是为了防止 负数对于下面if条件的判断
            int num = Math.abs(nums[i]);

            if (num <= len) {

                //加绝对值是为了防止重复出现的数其上一次已经被置为负数
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return len + 1;
    }

    public static void main(String[] args) {
        Leetcode_41 leetcode_41 = new Leetcode_41();
        int[] nums = new int[]{3, 4, -1, 1};
        int i = leetcode_41.firstMissingPositive(nums);
        System.out.println(i);

    }
}
